﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Jayden.Dll.Core.Collections.Generic
{
	public class RedBlackTree
	{
		private RedBlackTree m_Parent;
		private RedBlackTree m_Left;
		private RedBlackTree m_Right;
		private bool m_IsBlack;

		public bool IsBlack { get { return m_IsBlack; } }
		public bool IsRed { get { return !m_IsBlack; } }

		public RedBlackTree GrandParent
		{
			get
			{
				if (m_Parent != null)
					return m_Parent.m_Parent;
				return null;
			}
		}

		public RedBlackTree Uncle
		{
			get
			{
				RedBlackTree grandParent = GrandParent;
				if (grandParent == null)
					return null;
				if (m_Parent == grandParent.m_Left)
					return grandParent.m_Right;
				return grandParent.m_Left;
			}
		}

		private void InsertCase1()
		{
			if (m_Parent == null)
				m_IsBlack = true;
			else
				InsertCase2();
		}

		private void InsertCase2()
		{
			if (m_Parent.m_IsBlack)
				return;
			else
				InsertCase3();
		}

		private void InsertCase3()
		{
			RedBlackTree uncle = Uncle;
			if (uncle != null && !uncle.m_IsBlack)
			{
				m_Parent.m_IsBlack = true;
				uncle.m_IsBlack = true;
				RedBlackTree grandParent = GrandParent;
				grandParent.m_IsBlack = false;
				grandParent.InsertCase1();
			}
			else
				InsertCase4();
		}

		private void InsertCase4()
		{

		}

	}
}
